package com.dycong.common.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * 作用描述:给定一个没有重复数字的序列，返回其所有可能的全排列。
 * <p>
 * 示例:
 * <p>
 * 输入: [1,2,3]
 * 输出:
 * [
 * [1,2,3],
 * [1,3,2],
 * [2,1,3],
 * [2,3,1],
 * [3,1,2],
 * [3,2,1]
 * ]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/permutations
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author dycong
 * @date 2019/12/19 8:15
 */
public class Permute_46 {

    public static void main(String[] args) {
        Permute_46 permute_46 = new Permute_46();
        permute_46.permute(new int[]{1, 2, 3, 4, 5, 6, 7, 88, 9}).forEach(System.out::println);
    }

    /**
     * 方法1：回溯法
     * 回溯法
     * 是一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认 不是 一个解的话（或者至少不是 最后一个 解），回溯算法会通过在上一步进行一些变化抛弃该解，即 回溯 并且再次尝试。
     * <p>
     * 这里有一个回溯函数，使用第一个整数的索引作为参数 backtrack(first)。
     * <p>
     * 如果第一个整数有索引 n，意味着当前排列已完成。
     * 遍历索引 first 到索引 n - 1 的所有整数。Iterate over the integers from index first to index n - 1.
     * 在排列中放置第 i 个整数，
     * 即 swap(nums[first], nums[i]).
     * 继续生成从第 i 个整数开始的所有排列: backtrack(first + 1).
     * 现在回溯，即通过 swap(nums[first], nums[i]) 还原.
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> permute(int[] nums) {
        // init output list
        List<List<Integer>> output = new LinkedList();

        // convert nums into list since the output is a list of lists
        ArrayList<Integer> nums_lst = new ArrayList<Integer>();
        for (int num : nums) {
            nums_lst.add(num);
        }

        int n = nums.length;
        backtrack(n, nums_lst, output, 0);
        return output;
    }

    public void backtrack(int n,
                          ArrayList<Integer> nums,
                          List<List<Integer>> output,
                          int first) {
        // if all integers are used up
        if (first == n) {
            output.add(new ArrayList<Integer>(nums));
            return;
        }
        for (int i = first; i < n; i++) {
            // place i-th integer first
            // in the current permutation
            Collections.swap(nums, first, i);
            // use next integers to complete the permutations
            backtrack(n, nums, output, first + 1);
            // backtrack
            Collections.swap(nums, first, i);
        }
    }
}
